# 小顶堆

def swap(arr, a, b):
    arr[a], arr[b] = arr[b], arr[a]
    print(arr)


def heapify(arr, heap_len, cur):

    tar = cur  # 当前最小/最大值

    left = 2*cur+1
    if left < heap_len and arr[left] < arr[tar]:
        tar = left

    right = 2*cur+2
    if right < heap_len and arr[right] < arr[tar]:
        tar = right

    if tar != cur:
        swap(arr, tar, cur)
        heapify(arr, heap_len, tar)


def heap_sort(arr):
    heap_len = len(arr)
    for i in range(heap_len//2-1, 0, -1):  # 从最后一个非叶子节点开始向上构建堆
        heapify(arr, heap_len, i)

    while heap_len != 0:
        heapify(arr, heap_len, 0)
        heap_len -= 1
        swap(arr, 0, heap_len)


if __name__ == '__main__':
    heap_sort([1, 2, 3, 4, 5][::-1])
